import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:前K个高频元素、最小K个数、前k个高频单词、两数相加（链表）
 * Date: 2024-02-12
 * Time:23:01
 */
public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums) {
            map.put(num, map.getOrDefault(num,0)+1);
        }

        PriorityQueue<Map.Entry<Integer,Integer>> q = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
            if(q.size() < k) {
                q.offer(entry);
            } else {
                if(q.size() == k) {  //比较Value（出现频次）
                    Map.Entry<Integer,Integer> top = q.peek();
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        q.poll();
                        q.offer(entry);
                    }
                }
            }
        }
        int[] ret = new int[k];
        for(int i = 0;i < k;i++) {
            ret[i] = q.poll().getKey();
        }
        return ret;
    }


    /////////////////////////////////////////////////////////////
    //最小K个数
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k == 0)
            return ret;


        Comparator<Integer> maxHeap = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        };

        PriorityQueue<Integer> q = new PriorityQueue<>(maxHeap);
        for(int num:arr) {
            if(q.size()<k) {
                q.offer(num);
            } else {
                if(q.size() == k) {
                    if (num < q.peek()) {
                        q.poll();
                        q.offer(num);
                    }
                }
            }
        }

        for(int i = 0;i<k;i++) {
            ret[i] = q.poll();
        }
        return ret;
    }


    /////////////////////////////////////////////////////////
    //前k个高频单词
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();  //单词及出现次数
        for(String str:words) {
            map.put(str, map.getOrDefault(str,0)+1);
        }

        //建立小堆
        PriorityQueue<Map.Entry<String ,Integer>> q =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if(o1.getValue() == o2.getValue()) {
                            return o1.getKey().compareTo(o2.getKey());  //按照字典序排序
                        }
                        return o2.getValue().compareTo(o1.getValue());
                    }
                });
        //随便放k个进去
        for(Map.Entry<String ,Integer> entry:map.entrySet()) {
            if(q.size() == k) {
                Map.Entry<String ,Integer> top = q.peek();
                if(entry.getValue().compareTo(top.getValue()) == 0) {
                    if(entry.getKey().compareTo(top.getKey()) < 0) {
                        q.poll();
                        q.offer(entry);
                    }
                } else if(entry.getValue() > top.getValue()){
                        q.poll();
                        q.offer(entry);
                }
            } else {
                q.offer(entry);
            }


        }
        List<String> ret = new ArrayList<>();
        for(int i =  0;i < k;i++) {
            String str = q.poll().getKey();
            ret.add(str);
        }
        List<String> ret1 = new ArrayList<>();
        for(int j = k-1;j >= 0;j--) {
            ret1.add(ret.get(j));
        }
        return ret1;
    }
//////////////////////////////////////////////////////////////
    //两数相加
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();  //哨兵节点
        //相加，如果和超过10，就进1
        //l1和l2不一定等长
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        int flag = 0;  //标记下一位用不用进1
        ListNode head = dummy;  //新链表的头
        ListNode prev = head;
        while(cur1 != null || cur2 != null) {
            int val1 = 0,val2 = 0;
            if(cur1 != null) {
                val1 = cur1.val;
            }
            if(cur2 != null) {
                val2 = cur2.val;
            }
            int sum = val1 + val2 + flag;
            int digit = sum % 10; //每个节点要存放的数位
            flag = sum / 10;
            ListNode node = new ListNode(digit);

            //把node和前面的节点连起来
            prev.next = node;
            prev = node;

            if(cur1 != null)
                cur1 = cur1.next;
            if(cur2 != null)
                cur2 = cur2.next;
        }
        if(flag == 1) {
            ListNode node = new ListNode(1);
            prev.next = node;
        }

        return head.next;


/*
        //此时prev指向最后一个节点
        ListNode notNullList = cur2 == null ? cur1 : cur2;
        while(notNullList != null) {
            ListNode node = new ListNode(notNullList.val);
            node = prev.next;
            prev = node;
            notNullList = notNullList.next;
        }
*/

    }

}
